#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 32005;
const int M = 65;

int n,m;
LL dp[N];
LL price[M],val[M];
vector<int> son[M];
bool ignores[M];

int main(){
    scanf("%d%d",&n,&m);
    int p,v,fa;
    memset(ignores,0,sizeof(ignores));
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%d",&p,&v,&fa);
        price[i] = p;
        val[i] = p*v;
        if(fa!=0){
        	son[fa].emplace_back(i);
        	ignores[i] = true;
		}
    }
    memset(dp,0,sizeof(dp));
    LL v0,v1,v2,v3;
    for(int i=1;i<=m;i++){
    	if(ignores[i]) continue;
        for(int j=n;j>=price[i];--j){
        	// v0=dp[j-price[i]]+val[i];
        	//
        	dp[j]=max(dp[j], dp[j-price[i]]+val[i]);
			if(son[i].size()==1){
				if(j>=price[i]+price[son[i][0]]){
					v1 = dp[j-price[i]-price[son[i][0]]]+val[i]+val[son[i][0]];
					dp[j] = max(dp[j],v1);
				}
			}
			else if(son[i].size()==2){
				v1=v2=v3=0;
				if(j>=price[i]+price[son[i][0]]){
					v1=dp[j-price[i]-price[son[i][0]]]+val[i]+val[son[i][0]];
				}
				if(j>=price[i]+price[son[i][1]]){
					v2=dp[j-price[i]-price[son[i][1]]]+val[i]+val[son[i][1]];
				}
				if(j>=price[i]+price[son[i][0]]+price[son[i][1]]){
					v3=dp[j-price[i]-price[son[i][0]]-price[son[i][1]]]+val[i]+val[son[i][0]]+val[son[i][1]];
				}
				dp[j]=max(max(dp[j],v1),max(v2,v3));
			}
        }
    }
    printf("%d\n",dp[n]);
    return 0;
}
